/**
 * @file 006.排序素组中两个数字之和.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-06
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    vector<int> twoSum(const vector<int> &numbers, int target)
    {
        // 枚举 + 二分 O(NlogN)
#if 0
        int n = numbers.size();
        for (int i = 0; i < n - 1; ++i) {
            int j = i + 1, k = n - 1;
            while (j <= k) {
                int mid = (j + k) / 2;
                if (numbers[i] + numbers[mid] == target) {
                    return {i, mid};
                } else if (numbers[i] + numbers[mid] < target) {
                    j = mid + 1;
                } else {
                    k = mid - 1;
                }
            }
        }
        return {-1, -1};
#endif
        // 双指
        int n = numbers.size();
        int i = 0, j = n - 1;
        while (i < j) {
            if (numbers[i] + numbers[j] == target) {
                return {i, j};
            } else if (numbers[i] + numbers[j] < target) {
                ++i;
            } else {
                --j;
            }
        }
        return {-1, -1};
    }
};

int main()
{
    print(Solution().twoSum({1, 2, 4, 6, 10}, 8));
    print(Solution().twoSum({2, 3, 4}, 6));
    print(Solution().twoSum({-1, 0}, -1));
    return 0;
}